package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class Q0380 {
    HashMap<Integer, Integer> map;
    ArrayList<Integer> list;
    Random random;

    //    public RandomizedSet() {
    public Q0380() {
        map = new HashMap<>();
        list = new ArrayList<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        int last = list.get(list.size() - 1);
        list.set(index, last);
        list.remove(list.size() - 1);
        map.put(last, index);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}